exports.run = function(nfa, str) {
  const {state_map, transition_map} = nfa
  let current_states = new Set()
  let next_states = new Set()

  addState(current_states, state_map.get(nfa.start))

  for (let ch, i = 0, len = str.length; i < len; i++) {
    ch = str[i]
    step(ch)
    let tmp = current_states
    current_states = next_states
    next_states = tmp
  }

  function step(ch) {
    next_states.clear()
    current_states.forEach((state) => {
      // input transition's from state only have 1 transition
      if (state.transitions.length !== 1) return
      let transition = transition_map.get(state.transitions[0])
      if (transition.input === ch) {
        addState(next_states, state_map.get(transition.to))
      }
    })
  }

  function addState(set, state) {
    if (!state || set.has(state)) {
      return
    }

    // epsilon transition
    if (isEpsilonTransition(transition_map.get(state.transitions[0]))) {
      addState(set, getStateByto(state.transitions[0]))
      addState(set, getStateByto(state.transitions[1]))
    } else {
      set.add(state)
    }
  }

  function isEpsilonTransition(transition) {
    if (!transition) return false
    return !transition.input
  }

  function getStateByto(transition_id) {
    if (transition_id === undefined) return null
    return state_map.get(transition_map.get(transition_id).to)
  }

  // check if end state in current_states
  for (let state of current_states) {
    if (state.transitions.length === 0) return true
  }
  return false
}

exports.runWithBacktrack = function(nfa, str) {
  const {state_map, transition_map} = nfa
  const transition_path = [] // [transition_id, ...]

  let char_index = 0
  let current_state = state_map.get(nfa.start)
  let next_transition = transition_map.get(current_state.transitions[0])

  const NEXT = 1
  const BACK = -1
  const FINISH = 0

  while (true) {
    let result = forward()
    if (result === BACK) {
      if (back() === FINISH) break
    } else if (result === FINISH) {
      break
    }
  }

  function forward() {
    if (!next_transition) return BACK
    // epsilon
    if (!next_transition.input) {
      transition_path.push(next_transition)
      current_state = state_map.get(next_transition.to)
      next_transition = transition_map.get(current_state.transitions[0])
      return NEXT
    }
    if (next_transition.input === str[char_index]) {
      char_index++
      transition_path.push(next_transition)
      current_state = state_map.get(next_transition.to)
      if (char_index === str.length) {
        return FINISH
      } else {
        next_transition = transition_map.get(current_state.transitions[0])
        return NEXT
      }
    } else {
      // not match
      return BACK
    }
  }

  function back() {
    if (!current_state) return FINISH
    const last_transition_id = current_state.transitions[1]
    // already try all transitions
    if (last_transition_id === undefined || last_transition_id === next_transition.id) {
      // go back
      next_transition = transition_path.pop()
      if (!next_transition) {
        current_state = null
        return FINISH
      }
      // move back if has valid input char
      if (next_transition.input) {
        char_index--
      }
      current_state = state_map.get(next_transition.from)
      return back()
    }
    next_transition = transition_map.get(last_transition_id)
    return NEXT
  }

  // check if current state is end state, or can go directly to end state only with epsilon transitions

  const reachable_states = new Set()
  
  addState(current_state)

  function addState(state) {
    if (!state) return
    if (reachable_states.has(state)) return
    reachable_states.add(state)
    state.transitions.forEach((id) => {
      // only add epsilon transiton's to state
      let transition = transition_map.get(id)
      if (transition.input === '') {
        addState(state_map.get(transition.to))
      }
    })
  }

  let matched = false
  let xx = ''
  reachable_states.forEach((state) => {
    // end state
    state.transitions.forEach((id)=>{
      xx += transition_map.get(id).input;
    })
    if (state.transitions.length === 0) {
      matched = true
    }
  })
  
  
  return matched
}

exports.run2= function (nfa,str){
  let string = str+'#';
  let begin = false
  const {state_map, transition_map} = nfa
  const result = []
  let index = 0;
  let currenTrans = getTransition(nfa.start);
  let tempString = ''
  while(index<string.length && string !==''){
    let token = string[index];
    // whileChild(token)
    const tempCurrenTrans = currenTrans;
    if(tempCurrenTrans.length === 1){
      // if(tempCurrenTrans[0].input === ''){
      //   beginReg(false)
      //   break
      // }
      const bool = solo(tempCurrenTrans[0],token)
      if(bool === false){
        index = -1;
        string = string.slice(1)
      }
    }else if(tempCurrenTrans.length === 2){
      const bool = Asterisk(tempCurrenTrans,token);
      if(bool===false)index--
    }else if(tempCurrenTrans.length ===0){
      beginReg(false)
      if(tempString !== ''){
        result.push(tempString)
        tempString = ''
      }
      currenTrans = getTransition(nfa.start);
    }
    index++
  }
  if(tempString !== '' && !begin){
    result.push(tempString)
    tempString = ''
  }
  //全部是字符 'abcde...'
  function solo(tran,token){
    if(tran.input === token){
      tempString += token;
      const to = tran.to;
      currenTrans = getTransition(to);
      beginReg(true)
      return true;
    }else{
      tempString = ''
      currenTrans = getTransition(nfa.start);
      beginReg(false)
      return false
    }
  }
  // *  |
  function Asterisk(trans,token){
    currenTrans = []
    const tran1 = trans[0]
    const tran2 = trans[1]
    if(tran1.input === token){
      tempString += token;
      // currenTrans = getTransition(tran1.to);
      currenTrans = getTransition(tran1.to);
      
      beginReg(true)
      return true;
    }else{
      currenTrans = tran2? [tran2]:[];
      return false;
    }
  }

  function getTransition(stateId){
    let transitions = []
    const transitionIds = state_map.get(stateId).transitions;
    //如果为空直接返回
    if(transitionIds.length ===0){
      return transitions
    }
    transitionIds.forEach(id =>{
      let tran = transition_map.get(id);
      //如果input为空那么再次递归查询
      if(tran.input === ''){
        tran = getTransition(tran.to)[0]
      }
      transitions.push(tran)
    })
    
    return transitions
  }
  function getType(currens){
    let val = ''
    currens.forEach(tran =>{
      if(tran.input === '') val +='*'
    })
    return val
  }
  function beginReg(bool){
    begin = bool;
  }
  return result;
}